package LC;

/**
 * https://leetcode.com/problems/linked-list-cycle/description/
 * Given a linked list, determine if it has a cycle in it.
 * Follow up:
 * Can you solve it without using extra space?
 */
public class LC_141_LinkedListCycle_LinkedList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = head;
        System.out.println(Solution.hasCycle(head));
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    static class Solution {
        static boolean hasCycle(ListNode head) {
            if (head == null || head.next == null)
                return false;
            ListNode curr = head;
            ListNode sec = head;

            while (sec.next != null && sec.next.next != null) {
                curr = curr.next;
                sec = sec.next.next;
                if (curr == sec) return true;
            }
            return false;
        }
    }
}